CS254 Spring 2003Practice Final

The practice final is below. Here are some facts about the actual final: (a) The final will be in class Monday, May 19 from 5:15pm to 7:30pm. (b) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (c) It has six problems and will cover the whole semester's material. Of these six problem one will be from before the first midterm, one from between midterm 1 and 2, and the remaining problem will be from after the second midterm.(d) You should bring photo ID. (e) There will be more than one version of the test. Each version will be of comparable difficulty. (f) If your cell-phone or beeper goes off you will be excused from the test at that point and graded on what you have done till your excusal. (g) One problem (less typos) on the actual test will be from the practice test.

1. Prove that BPP is contained in Σ^p₂.

2. Prove directly that coNP is in IP.

3. Show that for any fixed k there is a language in Σ^p₄ that does not have circuits of size n^k.

4. Show that if any sparse language is NP-complete that P=NP.

5. Give an oracle relative to which P=BPP.

6. Give an oracle relative to which one way functions exist.

7. Show that the language consisting of boolean expressions which have unique satisfying assignments is in BH(2). Prove that if it is in NP then NP=coNP.

8. Show that if PH=PSPACE then LOGSPACE is not equal to NP.

9. Prove that the problem of determining if the maximum clique in a graph has size k can be done in P^NP but where only logarithmically many oracle calls are made.

10. Prove IP is contained in PSPACE.